#include <stdio.h>

#define INF 0x3f3f3f
#define MAXV 6

typedef struct Graph
{
    int n;
    int edges[MAXV][MAXV];
} Graph;

typedef struct EdgeType
{
    int v1;
    int v2;
    int weight;
} EdgeType;

void insertSort(EdgeType E[], int n)
{
    int i, j;
    for (i = 1; i < n; i++)
    {
        EdgeType temp = E[i];
        for (j = i - 1; j >= 0 && E[j].weight > temp.weight; j--)
        {
            // 大数后移一位
            E[j + 1] = E[j];
        }
        E[j + 1]= temp;
    }
}

// Kruskal
void kruskal(Graph g)
{
    // 有MAXV个顶点的无向图最多有MAXV * (MAXV - 1) / 2条边
    EdgeType E[MAXV * (MAXV - 1) / 2];
    int vest[MAXV];

    // 构建所有边
    // 遍历邻接矩阵的上三角部分
    int m = 0;  // 用于存储边的索引
    for (int i = 0; i < g.n; i++) {
        for (int j = i + 1; j < g.n; j++) {
            if (g.edges[i][j] != INF && g.edges[i][j] != 0) {
                E[m].v1 = i;
                E[m].v2 = j;
                E[m].weight = g.edges[i][j];
                m++;
            }
        }
    }
    // 对E[]按照边的权值从小到大排序
    insertSort(E, m);

    // 初始化并查集
    for (int i = 0; i < g.n; i++)
    {
        vest[i] = i;
    }
    

    // 遍历E[]，依次将边加入最小生成树中
    int count = 1;  // 记录加入最小生成树的边数
    m = 0;
    while (count <= g.n - 1) // 共有n-1条边
    {
        // 依次取出数组中的边
        int v1 = E[m].v1;
        int v2 = E[m].v2;
        if (vest[v1] != vest[v2]) {
            printf("from %d to %d weight: %d\n", v1, v2, E[m].weight);
            // 统一并查集编号
            for (int i = 0; i < g.n; i++)
            {
                if (vest[i] == vest[v2]) {
                    vest[i] = vest[v1];
                }
            }
            count++;
        }
        m++;
    }
}


// 构建无向图
void createGraph(Graph *g)
{
    int i, j;
    g->n = MAXV;
    int adjMatrix[MAXV][MAXV] = {
        {0, 6, 1, 5, INF, INF},
        {6, 0, 5, INF, 3, INF},
        {1, 5, 0, 5, 6, 4},
        {5, INF, 5, 0, INF, 2},
        {0, 3, 6, INF, 0, 6},
        {INF, INF, 4, 2, 6, 0}};
    for (i = 0; i < MAXV; i++)
    {
        for (j = 0; j < MAXV; j++)
        {
            g->edges[i][j] = adjMatrix[i][j];
        }
    }
}

int main()
{
    Graph g;
    createGraph(&g);
    kruskal(g);
    return 0;
}
